package com.github.hgkmail.hello.leetcode101.sort;

import java.util.*;

public class LC451SortCharactersByFrequency {
    public String frequencySort(String s) {
        //base case
        if(s.length()<=0) {
            return "";
        }
        char[] sChars = s.toCharArray();
        Map<Character, Integer> counts = new HashMap<>();
        for (int i = 0; i < sChars.length; i++) {
            counts.put(sChars[i], counts.getOrDefault(sChars[i], 0)+1);
        }
        PriorityQueue<Map.Entry<Character, Integer>> heap = new PriorityQueue<>(sChars.length, new Comparator<Map.Entry<Character, Integer>>() {
            @Override
            public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
                return o2.getValue()-o1.getValue();
            }
        });
        counts.entrySet().forEach(i->heap.offer(i));
        StringBuilder sb=new StringBuilder();
        while (!heap.isEmpty()) {
            Map.Entry<Character, Integer> entry = heap.poll();
            for (int i = 0; i < entry.getValue(); i++) {
                sb.append(entry.getKey());
            }
        }

        return sb.toString();
    }
    public static void main(String[] args) {
        System.out.println(new LC451SortCharactersByFrequency().frequencySort("Aabb"));
    }
}
